1. Field of the Invention
The present invention relates to apparatus and methods for the coding, storing, and transmitting of graphical information. More particularly, the present invention relates to apparatus and methods for generating, storing and/or transmitting coded representations of high fidelity graphic art images suitable for the photocomposition of printed materials, for facsimile, and for other similar applications.
2. Description of the Prior Art
General Prior Art
Recent years have witnessed greatly increased usage of automatic means for composing and printing page copy for use in directories, catalogs, magazines and other printed works. An important aspect of such photocomposition schemes is the coding and storage of machine-compatible signals representative of graphical source information. In particular, when pictorial information and/or high-resolution type fonts are to be used, it has been found necessary to identify, by scanning with great particularity, the individual graphical entities associated with the source material. To permit the further processing of these data it has usually been necessary to store them in memories having substantial capacity. Often these data are stored for long times, as when they are to be used in successive issues of a book, magazine or the like. Because typical published materials, especially photographic or other picture materials are so diverse, and because the information content of such materials is so great, the volume of data required to be stored is potentially very large. It is especially important therefore that these data be stored in as efficient a manner as possible.
In other applications, it may be desired that printed or graphic art information to be transmitted to a remote location and there be photocomposed, displayed, printed, or otherwise employed. In such applications, it may not be necessary to store the coded information at either the sending or the receiving ends. Nevertheless, it is important that the coding of such graphic source information be simple and inexpensive to implement as well as compact and conserving of transmission bandwidth.
A number of particular coding and storage schemes have been developed for efficiently storing and transmitting information. For example, the variable length codes described in Elias, "Predictive Coding", IRE Transactions Information Theory, March 1955, have proved to be useful in many variations. The well-known Huffman codes described, for example, in Huffman, "A Method for the Construction of Minimum Redundancy Codes," Proceedings IRE, Septemter 1952, pp. 1098-1101, and Fano, Transmission of Information, the MIT Press, 1961, pp. 75-81, offer optimum efficiency under particular circumstances. The application of these techniques to graphical information has generally been limited to one-dimensional coding, i.e., coding of signals associated with a single scan line in the source copy.
U.S. Pat. No. 3,461,231 issued Aug. 12, 1969, to R. V. Quinlan described a system for performing limited two-dimensional encoding. However, his techniques are limited to transmitting only an indication of the differences between data corresponding to two successive scan lines. A related technique is presented in Tyler, "Two Hardcopy Terminals for PCM Communications of Meteorological Products," Conference Record, 1969 International Conference on Communications, June 9-11, 1969, pp. 11-21 through 11-28. Tyler encodes his data (meteorological information) in terms of differential lengths for run lengths on two successive scan lines. Similarly, J. E. Elliot, U.S. Pat. No. 3,686,631 issued Aug. 22, 1972, describes a system which encodes the differences between data corresponding to successive scan lines, and S. Kagan et al, U.S. Pat. No. 3,347,981, issued Oct. 17, 1967, described a system with similar encoding, termed "exclusive transitions", which in some sense, relates to the second derivative of the transmitted image. Huang, in "Run-Length Coding and Its Extensions", Picture Bandwidth Compression, Huang and Tretiak (Eds.), Gordan and Breach, New York 1972, pp. 231-264, discusses some extensions to the work of Tyler.
Other two-dimensional coding of picture information is described in D. N. Graham, "Image Transmission by Two-Dimensional Contour Coding," Proceedings of the IEEE, Vol. 55, No. 3, March 1967, pp. 336-345.
The above-cited Quinlan and Tyler references indicate a need to determine not only what is encoded, i.e., which parameters are encoded, but also exactly how these parameters are to be encoded. The latter aspect of the problem is also treated in U.S. Pat. No. 3,643,019, issued Feb. 15, 1972, to J. P. Beltz. Particular reference is made by Beltz of the applicability of his techniques in commercial photocomposition systems such as the RCA VIDEOCOMP Series 70/800. Although Beltx applies a variable-length coding to segments defining a "zone", each such zone is the area defined by a single scan line. Beltz does not attempt to extend his results to two-dimensional coding. Likewise, though Graham and Huang speak of Huffman codes, their application is to very specific geometric entities.
Specific Prior Art
In the IEEE International Conference on Communications, June 1973, I have pesented a paper which describes a new method for encoding two-level images. This paper, which is entitled "High Fidelity Encoding of Two-Level, High Resolution Images", has been published in the Conference Record, IEEE International Conference on Communications, June 1973, Session 26, pp. 5-10. This method is considerably more compact than the above-described prior art methods because it decomposes a picture into large meaningful units, or entities, called "blobs", and defines those units in a unique manner which takes advantage of the statistics of the information.
In overview, the encoding process described in the above Conference Record publication consists of four phases. In the first phase, the image is scanned, sample, converted to digital form, and quantized into two brightness levels. In the second phase, the individual blobs are defined for both brightness levels, stored in intermediate form, and the pertinent blob statistics are collected. In the third phase, efficient codes based on the statistics collected in the second phase are determined and a determination is made also based on the statistics as to which brightness level will require the minimum number of coding bits. In the fourth phase, the intermediate form of the blobs of the determined brightness level is encoded with the codes derived from the third phase, generating thereby the various blob parameters.
With respect to the blob definition, in accordance with the published method, a blob is taken to consist of a number of runs of picture elements (pels) of the same level, which on successive runs satisfy the following conditions. Runs on two successive lines are part of the same blob if their run-beginnings are no more than J pels apart and their run-endings are no more than J pels apart and no two runs in the same line belong to the same blob. Experimentation has yielded an optimum J value of 3. A blob is encoded by encoding the length of the first run in the blob (the head run), the connection pattern of the run-beginnings and runendings of successive runs, if any, the blob position and the occurrence of the last run in the blob (called the tail run).
A more complete description of this encoding method can be found by perusing through the aforementioned Conference Record article which is herein incorporated by reference. A still more complete description of this encoding method may be found in my copending application Ser. No. 425,506 filed Feb. 12, 1973, which is also herein incorporated by reference.
The aforementioned blob encoding method which encodes one blob at a time is efficient in respect to the encoding bits requirements, and thus is conserving of storage space when the encoded information of a complete page of graphic data is desired to be stored. However, since in encoding the blob parameters each blob is fully encoded before the next blob is processed, the described method proves non-optimum for facsimile applications where it is desired to transmit information in real time (essentially), and where it is highly desirable to encode and to transmit information in a highly systemized manner, such as on a line by line basis, without depending on large storage means for storing the blobs information for a complete image page at a time.
It is an object of this invention, therefore, to employ the blob encoding in a facsimile mode of operation.
It is another object of this invention to employ a blob encoding method that is fast and simple.
It is a further object of this invention to encode the information of various blobs on a line by line basis.
It is a still further object of this invention to provide fast and efficient means for generating and transmitting the encoded information in essentially real time.
One method of blob encoding suitable for facsimile applications which is similar to the methods described herein is presented in "Efficient Coding of Two-Tone Image Ensembles", A. J. Frank et al, Proceedings, Missouri Symposium on Advanced Automation, University of Missouri, Columbia, Mo., April 14-16, 1975, pp. 87-94.